#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<assert.h>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
const int inf=1000000000;
const double pi=acos(-1.0);
#define eps (1e-15)
#define L (nod)<<1
#define R (nod)<<1|1
#define lson nod<<1,l,mid
#define rson nod<<1|1,mid+1,r
#define clr(x,a) memset(x,a,sizeof(x))
#define see(x)(cerr<<"[line:"<<__LINE__<<" "<<#x<<" "<<x<<endl)
#define se(x) cerr<<x<<" "
#define sz(x) (int)x.size()
#define pb push_back
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}

inline int to_i(const string& s)
{int n;sscanf(s.c_str(),"%d",&n);return n;}
inline string to_s(int n)
{char buf[32];sprintf(buf,"%d",n);return string(buf);}
inline int rd(){int x;scanf("%d",&x);return x;}

#define maxn  10030
const int maxe = 20010;
int n,m;
int nodeval[maxn],hash[maxn];

int first[maxn],next[maxe],E[maxe],Ef[maxe],C[maxe],id[maxe],M;
void init()
{	
	M=-1;
	clr(first,-1);
}
void _ins(int x,int y,int z,int p)
{
	M++;
	next[M]=first[x];
	first[x]=M;
	E[M]=y;Ef[M]=x;
	C[M]=z;id[M]=p;
}
void ins(int x,int y,int z,int p)
{
	_ins(x,y,z,p);
	_ins(y,x,z,p);
}

struct node
{
	int a,maxx;
}qtr[maxn*4],*tl,*head[maxn];
//trsz记录线段树大小,belong记录属于那棵线段树,head是线段树的头
int trsz[maxn],belong[maxn],pos[maxn];
//cas,vis是用于dfs ，dep记录深度,son记录儿子个数，
int cas,vis[maxn],dep[maxn],son[maxn],rmq[maxn][20],LOG=15;
void pushup(node *tr,int nod)
{
	tr[nod].maxx=max(tr[L].maxx,tr[R].maxx);
}
void insert(node *tr,int nod,int l,int r,int x,int y,int a)
{
	if(l==r)
	{
		tr[nod].maxx=tr[nod].a=a;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid)
		insert(tr,lson,x,y,a);
	if(mid<y)
		insert(tr,rson,x,y,a);
	pushup(tr,nod);
}

void maketree(int u,int h)
{
	int i,rt=u;
	for(i=1; i<h; i++)	rt=rmq[rt][0];//找到根 
	head[rt]=tl;
	for(i=0; i<h*4; i++)	//初始话树
		head[rt][i].a=head[rt][i].maxx=-inf;

	tl+=h*4;//偏移量加值
	trsz[rt]=h;//记录这颗树有多少个元素
	for(i=h; i>=1; i--)
	{
		belong[u]=rt;//当前节点属于那棵树
		pos[u]=i;//当前节点所在的这颗树第几个元素
		insert(head[rt],1,1,h,i,i,nodeval[u]);
		u=rmq[u][0];
	}
}

void change(int u,int b)//把节点u的值变为b
{
	u=hash[u];
	nodeval[u]=b;
	int rt=belong[u];
	insert(head[rt],1,1,trsz[rt],pos[u],pos[u],b);
}

int findmax(node *tr,int nod,int l,int r,int x,int y)
{
	if(x<=l && r<=y)
		return tr[nod].maxx;
	int mid=(l+r)/2,ans=-inf;
	if(x<=mid)	
		ans=max(ans,findmax(tr,lson,x,y));
	if(mid<y)
		ans=max(ans,findmax(tr,rson,x,y));
	return ans;
}
int getmax(int a,int b)//找最大值
{
	if(a==b)	return 0;
	int i,ans=-inf,fa,fb;
	while(a!=b)
	{
		fa=belong[a],fb=belong[b];
		if(fa!=fb)//不再同一条链
		{
		  ans=max(ans,findmax(head[fb],1,1,trsz[fb],1,pos[b]));	
			b=rmq[fb][0];
		}
		else
		{//因为点是被点上面的边映射到的，所以是pos[a]+1
	ans=max(ans,findmax(head[fb],1,1,trsz[fb],pos[a]+1,pos[b]));
			break;	
		}
	}
	return ans;
}

void dfs1(int u)//第一遍dfs，对边映射，并且找出每个节点的深度
{
	int i,j,e;
	vis[u]=cas;
	for(i=1; i<LOG; i++)	rmq[u][i]=rmq[rmq[u][i-1]][i-1];
	son[u]=1;
	for(e=first[u]; e!=-1; e=next[e])
	if(vis[E[e]]<cas)
	{
		int v=E[e];
		dep[v]=dep[u]+1;
		nodeval[v]=C[e];//把边权映射到点上
		hash[id[e]]=v;//把边和点对应
		rmq[v][0]=u;
		dfs1(v);
		son[u]+=son[v];
	}
}
void dfs2(int u,int h)//第二次dfs划分轻重边
{
	int i,j,e,v;
	vis[u]=cas;
	int now=-1,tp=0;
	for(e=first[u]; e!=-1; e=next[e])
	if(vis[E[e]]<cas && tp<son[E[e]])//找重边
	{
		tp=son[E[e]];
		now=E[e];
	}
	if(now==-1)	//找到一条重边的节点,建立线段树
	{
			maketree(u,h); 
			return ;	
	}
	
	dfs2(now,h+1);//找下一条重边
	for(e=first[u]; e!=-1; e=next[e])
	{
		v=E[e];
		if(vis[v]<cas && v!=now)
			dfs2(v,1);
	}
}
void split(int rt)//对一rt为根 的树进行树链划分
{
	tl=qtr;//头赋值
	cas++;//dfs的清零
	dep[rt]=1;//根节点
	nodeval[rt]=-inf;//对根节点初始化(因为边不能映射到此点)
	clr(rmq,0);
	dfs1(rt);	
	cas++;
	dfs2(rt,1);
}
int lca(int a,int b)//算出a 和b的公共祖先
{
	int i,tp=dep[b]-dep[a];
	if(tp<0)
	{	
		tp=-tp;
		swap(a,b);	
	}
	for(i=0; i<LOG; i++)
	if(tp&(1<<i)) b=rmq[b][i];
	if(a==b)return a;
	for(i=LOG-1; i>=0; i--)
	if(rmq[a][i]!=rmq[b][i])
	{
		a=rmq[a][i];
		b=rmq[b][i];
	}
	return rmq[a][0];
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	//freopen("out","w",stdout);
#endif
    int i,j,k,t,x,y,z;
	t=rd();
	while(t--)
	{
		n=rd();
		init();
		for(i=1; i<n; i++)
		{
			x=rd();y=rd();z=rd();
			ins(x,y,z,i);
		}
		split(1);
		int ans;
		char ch[20];
		while(1)
		{
			scanf("%s",ch);
	
			if(ch[0]=='D')	break;
			x=rd(); y=rd();
			if(ch[0]=='Q')
			{
				int fa=lca(x,y);
				ans=max(getmax(fa,x),getmax(fa,y));
				//由于是对边的处理，没有两个非重边情况处理
				printf("%d\n",ans);
			}
			else
			{
				change(x,y);
			}
		}
		
	}
}
